package com.zjs.algorithm;

import lombok.extern.slf4j.Slf4j;

/**
 * https://www.cnblogs.com/flyingdreams/p/11161157.html
 * 常见的排序算法：
 * 冒泡排序
 * 快速排序
 * 插入排序
 * 希尔排序
 * 选择排序
 * 堆排序
 * 二路归并排序
 * 多路归并排序
 * 基数排序
 * 桶排序
 * 计数排序
 */
@Slf4j
public class CommonSort {

    public static void main(String[] args) {
        int[] arr = new int[]{8,4, 5, 3, 7, 3};
//        int[] arr = new int[]{8,4};
        insertSort(arr);
        log.info("排序结果：{}", arr);
    }

    /**
     * 冒泡排序
     * 外层循环从1到n-1，内循环从当前外层的元素的下一个位置开始，依次和外层的元素比较，出现逆序就交换，通过与相邻元素的比较和交换来把小的数交换到最前面。
     * @param arr 数组
     */
    public static void bubblingSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * 思路：冒泡排序是通过相邻的比较和交换，每次找个最小值。选择排序是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
     * 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
     * @param arr
     */
    public static void chooseSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

    /**
     * 插入排序
     * 思路：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以理解为玩扑克牌时的理牌；
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int key = arr[j];
            while (j > 0 && arr[j - 1] > key) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = key;
        }
    }

    /**
     * 希尔排序
     * 思路：希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，
     * 待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
     * 问题：增量的序列取法？
     * 关于取法，没有统一标准，但最后一步必须是1；因为不同的取法涉及时间复杂度不一样，具体了解可以参考《数据结构与算法分析》；
     * 一般以length/2为算法。（再此以gap=gap*3+1为公式）
     */
    public static void shellSort(int[] arr) {
        for (int gap = arr.length/2; gap >= 1; gap = gap/2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                while(j - gap > 0) {
                    if (arr[gap] < arr[j -gap]) {
//                        int
                    }
                }
            }
        }
    }
}
